package com.yulongtian.weekCompetition.month202211.week2;

import java.util.ArrayList;
import java.util.List;

/**
 * 6234. 最小公倍数为 K 的子数组数目
 *
 * @author yulongTian
 * @create 2022-11-13 10:35
 */
public class Test02 {
    public static void main(String[] args) {
        int[] nums = {3, 6, 2, 7, 1};
        int k = 6;
        System.out.println(subarrayLCM(nums, k));
    }

    //方法一：暴力枚举
    public static int subarrayLCM(int[] nums, int k) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int g = 1;
            if (nums[i] > k || (k % nums[i]) != 0) {
                continue;
            }
            for (int j = i; j < nums.length; j++) {
                g = lcm(g, nums[j]);
                if (g == k) {
                    res++;
                }
            }
        }

        return res;
    }

    /**
     * 最大公约数
     * @param a
     * @param b
     * @return
     */
    public static int gcd(int a,int b){
        return b > 0 ? gcd(b,a%b) : a;
    }


    /**
     * 最小公倍数*最大公约数就是最小公倍数
     * @param a
     * @param b
     * @return
     */
    public static int lcm(int a,int b){
        return a / gcd(a,b) * b;
    }


}
